package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1035 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxUncrossedLines(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length;
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0) dp[i][j] = j == 0 ? (nums1[i] == nums2[j] ? 1 : 0) : (dp[i][j - 1] == 1 ? 1 : nums1[i] == nums2[j] ? 1 : 0);
                    else if (j == 0) dp[i][j] = i == 0 ? (nums1[i] == nums2[j] ? 1 : 0) : (dp[i - 1][j] == 1 ? 1 : nums1[i] == nums2[j] ? 1 : 0);
                    else if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }

            return dp[m - 1][n - 1];
        }
    }

    public void run() {
        System.out.println(new Solution().maxUncrossedLines(InputUtil.toIntegerArray("[1,4,2]"), InputUtil.toIntegerArray("[1,2,4]")));
        System.out.println(new Solution().maxUncrossedLines(InputUtil.toIntegerArray("[2,5,1,2,5]"), InputUtil.toIntegerArray("[10,5,2,1,5,2]")));
        System.out.println(new Solution().maxUncrossedLines(InputUtil.toIntegerArray("[1,3,7,1,7,5]"), InputUtil.toIntegerArray("[1,9,2,5,1]")));
    }

    public static void main(String[] args) throws Exception {
        LC1035 an = new LC1035();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
